#define _CRT_SECURE_NO_WARNINGS 1

/*
	返回链表的倒数第k个节点的值
*/

//快慢指针法
int kthToLast(struct ListNode* head, int k)
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (k--)
    {
        fast = fast->next;
    }
    while (fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow->val;
}


/*
        相交链表
        返回两链表的第一个相交节点
*/

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
    //先判断这两个链表是否相交
    struct ListNode* curA = headA;
    struct ListNode* curB = headB;
    int lenA = 1;
    int lenB = 1;
    while (curA->next)
    {
        curA = curA->next;
        lenA++;
    }
    while (curB->next)
    {
        curB = curB->next;
        lenB++;
    }
    //如果尾节点的地址不相同，说明这两个链表没有相交
    if (curA != curB)
    {
        return NULL;
    }
    //到了这里，说明这两个链表一定相交
    //求第一个相交的节点
    //假设法
    int gap = abs(lenA - lenB);
    struct ListNode* longlist = headA;
    struct ListNode* shortlist = headB;
    if (lenA < lenB)
    {
        //说明假设不成立
        longlist = headB;
        shortlist = headA;
    }
    while (gap--)
    {
        //先让长链表向前走两者长度的差值，使其可以从同一位置开始比较
        longlist = longlist->next;
    }
    while (longlist != shortlist)
    {
        longlist = longlist->next;
        shortlist = shortlist->next;
    }
    //出了该循环，说明这两者已经相等了
    return shortlist;
}